/**
* @description: 837. 新 21 点
* @author hewei
* @date 2022/9/5 15:42
* @version 1.0
*/

public class New21Game {

    public double new21Game(int n, int k, int maxPts) {
        double[] dp = new double[k + maxPts];
        double sum = 0;
        for (int i = k + maxPts - 1; i > k - 1; i--) {
            dp[i] = i >= n ? 0 : 1.0;
            sum += dp[i];
        }
        int r = 0;
        for (int i = k - 1; i >= 0; i--) {
            dp[i] = sum * (1.0 / maxPts);
            sum -= dp[k + maxPts - 1 - r++];
            sum += dp[i];
        }
        return dp[0];
    }
}
